//给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。 
//
// 
//
// 示例 1： 
//
// 
//输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
//输出：[1,2,3,6,9,8,7,4,5]
// 
//
// 示例 2： 
//
// 
//输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
//输出：[1,2,3,4,8,12,11,10,9,5,6,7]
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 10 
// -100 <= matrix[i][j] <= 100 
// 
// Related Topics 数组 矩阵 模拟 
// 👍 1003 👎 0


import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution54 {
    /**
     * 解题思路
     * 1.记录遍历二维数组的指针，根据规则变化指针的范围
     *
     *
     * 解答成功:
     * 			执行耗时:0 ms,击败了100.00% 的Java用户
     * 			内存消耗:39.7 MB,击败了5.03% 的Java用户
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        int rowLen = matrix.length, colLen = matrix[0].length, size = rowLen * colLen,
                recordIStart = 0, recordIEnd = matrix.length - 1,
                recordJStart = 0, recordJEnd = matrix[0].length - 1;

        List<Integer> result = new ArrayList<>(size);
        while(size > 0) {
            for(int j = recordJStart; j<= recordJEnd; j++) {
                result.add(matrix[recordIStart][j]);
                size--;
            }
            recordIStart++;
            if(size == 0) break;


            for(int i = recordIStart; i<=recordIEnd; i++) {
                result.add(matrix[i][recordJEnd]);
                size--;
            }
            recordJEnd--;
            if(size == 0) break;

            for(int j = recordJEnd; j>= recordJStart; j--) {
                result.add(matrix[recordIEnd][j]);
                size--;
            }
            recordIEnd--;
            if(size == 0) break;

            for(int i = recordIEnd; i>=recordIStart; i--) {
                result.add(matrix[i][recordJStart]);
                size--;
            }
            recordJStart++;

        }

        return result;
    }

    public static void main(String[] args) {
        int[][] arr = new int[][]{
                {1,2,3,4},
                {5,6,7,8},
                {9,10,11,12}
        };

        System.out.println(new Solution54().spiralOrder(arr));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
